package day190819;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/19 下午 02:46
 */
public class IsUgly {
    public boolean isUgly(int num) {
        if (num == 1) {
            return true;
        }
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        return num == 1;
    }

    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int two = 0, three = 0, five = 0;
        for (int i = 0; i < n; i++) {
            int min = Math.min(dp[two] * 2, Math.min(dp[three] * 3, dp[five] * 5));
            if (min == dp[two] * 2) {
                two ++;
            }
            if (min == dp[three] * 3) {
                three ++;
            }
            if (min == dp[five] * 5) {
                five ++;
            }
            dp[i] = min;
        }
        return dp[n - 1];
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxLength = 1;
        for (int i = 1; i < nums.length; i++) {
            int max = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] >= max) {
                    max = dp[j] + 1;
                }
            }
            dp[i] = max;
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] a = { 1,3,6,7,9,4,10,5,6 };
        IsUgly isUgly = new IsUgly();
        isUgly.lengthOfLIS(a);
    }


}
